#include "priority_queue.h"
#include <cstdlib>
#include <ctime>
#include <algorithm>

int nodeidx = 0;

bool isIncreasing(const std::vector<int> & arr)
{
    for(int i = 0; i < arr.size() - 1; i++)
        if(arr[i] > arr[i+1]) return false;
    return true;
}

int min(const std::vector<PriorityQueue<long long, int>::DataBase> &input)
{
    if(input.empty()) return 0x7fffffff;
    int res = input[0].data;
    for(auto x : input)
        if(x.data < res) res = x.data;
    return res;
}

void testBuildHeap()
{
    typedef PriorityQueue<long long, int>::DataBase db;
    static std::vector<db> input;
    printf("----------------------\n");
    printf("    BuildHeap Test    \n");
    printf("----------------------\n");
    printf("|    n    | time(ms) |\n");
    for(int n = 10; n <= 1000000; n *= 10)
    {
        for(int k = 0; k < n; k++)
            input.push_back( db((long long)(++nodeidx) * 19260817, rand()) );
        int initialtime = clock();
        PriorityQueue<long long, int> pq;
        pq.buildHeap(input);
        int timecost = (double) (clock() - initialtime) / CLOCKS_PER_SEC * 1000;
        printf("|%9d|%10d|\n", n, timecost);
        input.clear();
    }
    printf("----------------------\n\n");
}

void testHeapSort()
{
    typedef PriorityQueue<long long, int>::DataBase db;
    static std::vector<db> input;
    static std::vector<int> result;
    printf("-------------------------------\n");
    printf("         HeapSort Test         \n");
    printf("-------------------------------\n");
    printf("|    n    | time(ms) | result |\n");
    for(int n = 10; n <= 1000000; n *= 10)
    {
        for(int k = 0; k < n; k++)
            input.push_back( db((long long)(++nodeidx) * 19260817, rand()) );
        int initialtime = clock();
        PriorityQueue<long long, int> pq;
        pq.buildHeap(input);
        while(!pq.empty())
        {
            result.push_back(pq.top());
            pq.deleteMin();
        }
        int timecost = (double) (clock() - initialtime) / CLOCKS_PER_SEC * 1000;
        printf("|%9d|%10d|%s|\n", n, timecost, isIncreasing(result) ? "   AC   " : "   WA   ");
        input.clear();
        result.clear();
    }
    printf("-------------------------------\n\n");
}

void testRemove()
{
    typedef PriorityQueue<long long, int>::DataBase db;
    static std::vector<db> input;
    PriorityQueue<long long, int> pq;
    printf("------------------------------\n");
    printf("    Insert and Remove Test    \n");
    printf("------------------------------\n");
    printf("|  Key  |    Data    |\n");
    int n = 20;
    for(int k = 0; k < n; k++)
    {
        input.push_back( db((long long)k, rand()) );
        printf("|  %3lld  |%11d |\n", input.back().key, input.back().data);
        pq.insert(input.back());
    }
    std::random_shuffle(input.begin(), input.end());
    printf("----------------------\n");
    for(int k = 0; k < n-1; k++)
    {
        pq.remove(input[k].key);
        printf("Remove Key %2lld,  pq.top()=%d\n", input[k].key, pq.top());
    }
    printf("----------------------------------------\n\n");
}

void testModify()
{
    typedef PriorityQueue<long long, int>::DataBase db;
    static std::vector<db> input;
    PriorityQueue<long long, int> pq;
    printf("------------------------------\n");
    printf("    Insert and Modify Test    \n");
    printf("------------------------------\n");
    printf("|  Key  |    Data    |\n");
    int n = 10;
    for(int k = 0; k < n; k++)
    {
        input.push_back( db((long long)k, rand()) );
        printf("|  %3lld  |%11d |\n", input.back().key, input.back().data);
        pq.insert(input.back());
    }
    printf("----------------------\n");
    for(int k = 0; k < 20; k++)
    {
        int tmp = rand();
        long long key = rand() % 10;
        pq.modifyData(key, tmp);
        input[key] = db(key, tmp);
        printf("Modify Key %2lld Set Data=%11d,  pq.top()=%d, %s\n", key, tmp, pq.top(), pq.top() == min(input) ? "AC" : "WA");
    }
    printf("-----------------------------------------------------------\n\n");
}

void testMerge()
{
    typedef PriorityQueue<long long, int>::DataBase db;
    static std::vector<db> input;
    static std::vector<int> result;
    printf("-------------------------------\n");
    printf("          Merge  Test          \n");
    printf("-------------------------------\n");
    printf("|    n    | time(ms) | result |\n");
    for(int n = 10; n <= 1000000; n *= 10)
    {
        //首先建立两个大小为n的优先队列
        for(int k = 0; k < n; k++)
            input.push_back( db((long long)(++nodeidx) * 19260817, rand()) );
        PriorityQueue<long long, int> pq;
        pq.buildHeap(input);
        input.clear();
        for(int k = 0; k < n; k++)
            input.push_back( db((long long)(++nodeidx) * 19260817, rand()) );
        PriorityQueue<long long, int> pq2;
        pq2.buildHeap(input);
        input.clear();

        //将两个优先队列合并到pq
        int initialtime = clock();
        pq.merge(pq2);
        //记录合并用时以验证效率
        int timecost = (double) (clock() - initialtime) / CLOCKS_PER_SEC * 1000;
        //通过测试堆排序结果来验证合并的正确性
        while(!pq.empty())
        {
            result.push_back(pq.top());
            pq.deleteMin();
        }
        printf("|%9d|%10d|%s|\n", n, timecost, isIncreasing(result) ? "   AC   " : "   WA   ");
        result.clear();
    }
    printf("-------------------------------\n\n");
}

int main()
{
    srand(time(0));
    testBuildHeap();
    testHeapSort();
    testRemove();
    testModify();
    testMerge();
    return 0;
}